home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.mactech.com 2010
/
ftp.mactech.com.tar
/
ftp.mactech.com
/
challenge
/
13.06
/
ChallengeHexGame.sit.hqx
/
Challenge, Hex Game
/
Dynamic Memory4.c
next >
Wrap
Text File
|
1997-05-07
|
5KB
|
204 lines
typedef struct Header
{
long
size; // the size in bytes of the block
struct Header
*prev, // the previous block's header
*next; // the next block's header
} Header;
void InitializeHeap(Header *heapStart, long size);
void ChopBlock(Header *theBlock, long fragSize);
void *AllocateBlock(long size);
void FuseBlocks(Header *block);
void FreeBlock(void *data);
void HeapSummary(void);
Boolean IsPointerValid(void *data);
void SetHeap(Header *start);
Header *GetHeap(void);
Header
*gHeapStart;
long
gFreeBlocks,
gUsedBlocks,
gFreeSpace,
gUsedSpace,
gTotalSpace;
void InitializeHeap
(
// these are assumed to be valid; no error-checking is performed
Header *heapStart, // the address of the start of the heap zone
long size // the size of the zone
)
{
heapStart->size = size - sizeof (Header); // mark the size of the zone
heapStart->prev = nil; // mark as being the first block…
heapStart->next = nil; // …and the last
gHeapStart = heapStart; // initialize the global heap start pointer
}
void ChopBlock
(
// these are assumed to be valid; fragSize must be less than theBlock->size
Header *theBlock, // the block to chop
long fragSize // the size of the first new fragment
)
{
Header
*newBlock;
newBlock = (Header *) (((char *) theBlock) + sizeof (Header) + fragSize);
newBlock->size = theBlock->size - fragSize - sizeof (Header); // the remaining space
newBlock->prev = theBlock; // newBlock comes after theBlock
newBlock->next = theBlock->next; // it gets inserted between theBlock and theBlock->next
if (theBlock->next)
theBlock->next->prev = newBlock;
theBlock->size = fragSize; // theBlock gets just what was asked for
theBlock->next = newBlock; // its new next block is newBlock
}
void *AllocateBlock
(
long size // the size of the desired block
)
{
const long
BLOCK_IN_USE_MASK = 0x80000000, // if this bit is set in the 'size' field,
// the block is in use
MIN_BLOCK_SIZE = 80; // the smallest usable block (board data + pointers)
Header
*currentBlock; // a pointer to the block currently being considered
currentBlock = gHeapStart;
// loop until either there are no more blocks or a fitting one is found
while (currentBlock && ((currentBlock->size & BLOCK_IN_USE_MASK) || (currentBlock->size < size)))
currentBlock = currentBlock->next;
if (currentBlock) // a valid block was found
{
// if the block is much bigger than needed
if ((currentBlock->size - size) > (MIN_BLOCK_SIZE + sizeof (Header)))
ChopBlock(currentBlock, size); // cut off a piece of exactly the right size
currentBlock->size |= BLOCK_IN_USE_MASK; // mark as being in use
// return a pointer to just after the block header
return (char *) (currentBlock + 1);
}
else
// indicate that allocation failed
return nil;
}
void FuseBlocks
(
Header *block // the block to fuse with its following neighbor
)
{
Header
*neighbor;
neighbor = block->next;
block->next = neighbor->next;
neighbor->next->prev = block;
block->size += sizeof (Header) + neighbor->size; // blocks must not be in use
}
void FreeBlock
(
void
*data // the block of data to free, fusing with its neighbors if possible
)
{
const long
BLOCK_IN_USE_MASK = 0x80000000; // bit in size field used to indicate use of blocks
Header
*theBlock; // the data block's header
// the header is located just before the data
theBlock = ((Header *) data) - 1;
// assumed to be in use, with flag set; here it is reset
if (theBlock->size & BLOCK_IN_USE_MASK)
theBlock->size -= BLOCK_IN_USE_MASK;
// if there is a next block and it is free
if (theBlock->next && !(theBlock->next->size & BLOCK_IN_USE_MASK))
FuseBlocks(theBlock);
// if there is a previous block and it is free
if (theBlock->prev && !(theBlock->prev->size & BLOCK_IN_USE_MASK))
FuseBlocks(theBlock->prev);
}
void HeapSummary
(
void
)
{
const long
IN_USE_MASK = 0x80000000;
Header
*block;
block = gHeapStart;
while (block->next)
block = block->next;
gFreeBlocks = gUsedBlocks = gFreeSpace = gUsedSpace = 0;
while (block)
{
if (block->size & IN_USE_MASK)
{
gUsedBlocks++;
gUsedSpace += block->size - IN_USE_MASK;
}
else
{
gFreeBlocks++;
gFreeSpace += block->size;
}
block = block->prev;
}
gTotalSpace = (gFreeBlocks + gUsedBlocks) * sizeof (Header) + gFreeSpace + gUsedSpace;
}
Boolean IsPointerValid(void *data)
{
Header
*theBlock,
*compBlock;
theBlock = ((Header *) data) - 1;
compBlock = gHeapStart;
while(compBlock && compBlock != theBlock)
compBlock = compBlock->next;
if (compBlock == theBlock)
return true;
else
return false;
}
void SetHeap(Header *start)
{
gHeapStart = start;
}
Header *GetHeap(void)
{
return gHeapStart;
}